package org.review.algorithm.recursion;

import lombok.AllArgsConstructor;
import lombok.ToString;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 解决迷宫最短路径：
 * @1 深度优先策略 主要用到了递归，思路是找到相邻节点后一路跟踪下去，如果无路可走后后退一步继续寻找
 * @2 广度优先策略 需要用到队列的先进先出特性，主要是遍历当前节点的邻接节点，按照优先级将邻接节点添加到队列中，当前节点便利
 * 完后，从队列头取出一个元素，接着遍历邻接节点
 */
public class MiGong {

    public static void main(String[] args) {
        int[][] map = new int[8][7];

        System.out.println(map.length);
        System.out.println(map[0].length);
        //TODO 顶和底都是1 作为墙

        for (int i = 0; i < map.length; i++) {
            map[i][0] = 1;
            map[i][map[0].length - 1] = 1;
        }

        for (int i = 0; i < map[0].length; i++) {
            map[0][i] = 1;
            map[map.length - 1][i] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                System.out.print(map[i][j] + "  ");
            }
            System.out.println();
        }

      /*  System.out.println(way(map, 1, 1) + "输出小球走过的路径   ");

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                System.out.print(map[i][j] + "  ");
            }
            System.out.println();
        }*/


        int[] start = new int[]{1, 1};
        int[] end = new int[]{map.length - 2, map[0].length - 2};
        System.out.println(bfs(map, start, end));
       // System.out.println(dfs(map, 1, 1));
    }

    /**
     * 其实这个算是dfs 深度优先
     *
     * @param map
     * @param row
     * @param col
     * @return
     */
    public static boolean way(int[][] map, int row, int col) {

        if (map[6][5] == 2) { //todo 已经找到出口
            return true;
        } else {
            if (map[row][col] == 0) {
                map[row][col] = 2;
                if (way(map, row + 1, col)) { //todo 向下
                    return true;
                } else if (way(map, row, col + 1)) {//todo 向右
                    return true;
                } else if (way(map, row - 1, col)) {//todo 向上
                    return true;
                } else if (way(map, row, col - 1)) {//todo 向左

                    return true;
                } else {
                    map[row][col] = 3; //todo 走不通所以标注3
                    return false;
                }
            } else {
                return false;
            }
        }
    }

    //todo 使用depth 深度有限寻找最短路径 可能会出现死循环 依赖寻找的方向
    public static int dfs(int[][] map, int row, int col) {
        boolean[][] visited = new boolean[map.length][map[0].length];
        Stack<Point> stack = new Stack<>();
        stack.push(new Point(row, col, 0));
        visited[row][col] = true;
        int[][] DIRECTIONS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        int shortPath = Integer.MAX_VALUE;
        while (!stack.isEmpty()) {
            Point current = stack.pop();
            if (current.x == map.length - 2 && current.y == map[0].length - 2) {
                if (current.distance < shortPath) {
                    shortPath = current.distance;
                }
            }
            int distance = current.distance + 1;
            boolean flag = false;
            for (int[] direction : DIRECTIONS) {
                int newX = current.x + direction[0];
                int newY = current.y + direction[1];
                if (isValid(map, visited, newX, newY)) {
                    visited[newX][newY] = true;
                    stack.push(new Point(newX, newY, distance));
                    flag = true;
                    break;
                }
            }
            //todo 如果上一部没有找到可走的路径 就退回当前
            if (!flag) {
                visited[current.x][current.y] = false;
            }
        }
        return shortPath == Integer.MAX_VALUE ? -1 : shortPath;
    }
    //todo 使用bfs 广度优先求解 迷宫最短路径
    //todo  右 左 下 上 搜索，如果搜索到了以后放入队列里
    public static int bfs(int[][] maze, int[] start, int[] end) {
        int rows = maze.length;
        int cols = maze[0].length;
        int[][] DIRECTIONS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        boolean[][] visited = new boolean[rows][cols];
        Queue<Point> queue = new LinkedList<>();

        //todo 将起点加入队列
        queue.offer(new Point(start[0], start[1], 0));
        visited[start[0]][start[1]] = true;

        while (!queue.isEmpty()) {
            Point current = queue.poll();//todo 关键是这一步，从队列头广度搜索，一定是最短路径 优秀，如果改成深度优先，只需要调整direction 方向

            //todo 如果到达终点，返回当前距离
            if (current.x == end[0] && current.y == end[1]) {
                return current.distance;
            }

            // 遍历四个方向
            for (int[] direction : DIRECTIONS) {
                int newX = current.x + direction[0];
                int newY = current.y + direction[1];

                // 检查新位置是否合法
                if (isValid(maze, visited, newX, newY)) {
                    visited[newX][newY] = true;
                    queue.offer(new Point(newX, newY, current.distance + 1));
                }
            }
        }

        // 如果没有路径，返回-1
        return -1;
    }

    private static boolean isValid(int[][] map, boolean[][] visited, int x, int y) {
        int rows = map.length;
        int cols = map[0].length;
        return (x >= 0 && x < rows && y >= 0 && y < cols && map[x][y] == 0 && !visited[x][y]);
    }
}

@AllArgsConstructor
@ToString
class Point {
    int x, y, distance;
}
